﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions
{
    /*
     * The prime 41, can be written as the sum of six consecutive primes:
41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

     * */
    class Problem50 : IProblem
    {
        public string Calculate()
        {
            //taktika: bruteforce
            //u previousprimes dodajemo prosle primeove
            //   za svaki prime
            //      napravimo privremenu varijablu i oduzimamo prethodne primeove, count++ svaki put
            //   ako je rezultat > 0: ništa
            //   ako je rezultat 0 : gledamo maxCount
            //   ako je rezultat < 0: od početka dodajemo primeove, uz count++
            //       ako je rezultat > 0, nastavak
            //       ako je rezultat 0: gledamo maxCount

            int limit = 1000000;
            List<int> previousPrimes = new List<int>();

            int maxCount = 0;
            int targetPrime = 0;

            for (int i = 2; i < limit; i++)
            {
                if (CommonFunctions.IsPrime(i))
                {
                    int temp = i;

                    int trailingPointer = 0; //za pokazivat koju slijedeću dodat
                    int count = 0;
                    foreach (int p in previousPrimes)
                    {
                        count++;
                        temp -= p;

                        while (temp < 0)
                        {
                            temp += previousPrimes[trailingPointer];
                            trailingPointer++;
                            count--;
                        }

                        if (temp == 0)
                        {
                            if (count > maxCount)
                            {
                                maxCount = count;
                                targetPrime = i;
                                break;
                            }
                        }
                    }


                    //nakraju dodat u prethodne!
                    previousPrimes.Add(i);
                }
            }

            return targetPrime.ToString();
        }
    }
}
